11.1 פעולת אלגוריתם הופמן

מבנה נתונים ואלגוריתמים

 

 

הדיאגרמות הבאות מראות כיצד נבנה עץ בקידוד הופמן תוך שימוש באלגוריתם חמדני ישיר אשר בכל צעד משלב יחד את שני העצים בעלי המשקל הקטן ביותר.

 

 

הנתונים ההתחלתיים ממוינים לפי שכיחות:

 

 

שני בעלי המשקל הנמוך ביותר F ו- E משולבים יחד, ויוצרים תת-עץ במשקל 14. תת-העץ החדש מועבר למקומו הנכון:

 

 

 

שוב משולבים יחד שני בעלי המשקל הנמוך ביותר C ו- B ויוצרים תת-עץ במשקל 25. תת-העץ מועבר למקומו הנכון :

 

 

כעת תת-העץ שבמשקל 14 ו- D משולבים יחד יוצרים עץ במשקל 30, שמועבר למקומו הנכון:

 

 

כעת שני בעלי המשקל הנמוך ביותר הם תתי-העצים שבמשקלים 25 ו- 30, ושילובם מניב עץ במשקל 55. גם עץ זה מועבר למקומו בצד הנכון של A:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

לבסוף, משולבים A ותת-העץ שמשקלו 55 ויוצרים יחד את העץ הסופי.

 

 

 

 

      חזור ל: קוד הופמן                     חזור ל: תוכן עניינים